use std::fmt::{ Display };
use std::cmp::PartialEq;
use std::ops::Deref;

#[derive(Debug)]
struct Node<T: Display + PartialEq> {
    data: Option<T>,
    next: Option<Box<Node<T>>>
}

impl<T: Display + PartialEq> Node<T> {
    fn new(data: T) -> Node<T> {
        Node {
            data: Some(data),
            next: None
        }
    }
}


#[derive(Debug)]
pub struct Link<T: Display + PartialEq>{
    head: Node<T>
}

impl<T: Display + PartialEq> Link<T> {
    pub fn new() -> Link<T> {
        Link {
            head: Node {
                data: None,
                next: None
            }
        }
    }

    // 头插法
    pub fn create_link_for_head(&mut self, arr: Vec<T>) {
        for i in arr {
            let mut node = Node {
                data: Some(i),
                next: None,
            };

            // 从Option中取数据
            node.next = self.head.next.take();

            self.head.next = Some(Box::new(node));
        }
    }

    // 尾插法创建
    pub fn create_link_for_rear(&mut self, arr: Vec<T>, is_loop: bool) {
        // 初始化裸指针为空
        let mut rear: *mut Node<T> = std::ptr::null_mut();

        for i in arr {
            let node = Node::new(i);
            // 野指针
            let t = Box::into_raw(Box::new(node));

            if rear.is_null() {
                self.head.next =  Some(unsafe { Box::from_raw(t) });
                rear = t;
            } else {
                unsafe {
                    // 解引用裸指针
                    (*rear).next = Some(Box::from_raw(t));
                }
                rear = t;
            }
        }
    }
    // 在尾部插入 (采用遍历法,时间复杂度O(n)，不用遍历法的话就需要保存一个指向终端节点的尾指针,时间复杂度O(1))
    pub fn insert_by_rear(&mut self, data: T) {
        let node = Node::new(data);

        let mut current = &mut self.head.next;

        while let Some(ref mut node) = current {
            current = &mut node.next;
        }

        *current = Some(Box::new(node));
    }

    // 删除链表节点
    pub fn delete_node(&mut self, data: T) -> bool {
        let mut current = &mut self.head;

        while let Some(node) = current.next.as_mut() {
            if let Some(node_data) = &node.data {
                if *node_data == data {
                    current.next = node.next.take();

                    return true;
                }
            }

            current = current.next.as_mut().unwrap();
        }

        return false;
    }

    // 遍历
    pub fn display(&self) {
        let mut current = &self.head.next;

        while let Some(node) = current {
            if let Some(ref data) = node.data {
                print!("{} ", data);
            }

            current = &node.next;
        }
    }
}